class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution(object):
    def minimalExecTime(self, root):
        """
        :type root: TreeNode
        :rtype: float
        """

        def dfs(node):
            if node.left:
                a, b = dfs(node.left)
                if node.right:
                    c, d = dfs(node.right)
                    if a < c:
                        a, b, c, d = c, d, a, b
                    if a - 2 * b <= c:
                        return node.val + a + b,  (a + c) / 2
                    else:
                        return node.val + a + b, b + c
                else:
                    return a + node.val, b
            else:
                if node.right:
                    c, d = dfs(node.right)
                    return node.val + c, d
                else:
                    return node.val, 0

        a, b = dfs(root)
        return a - b

